МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” іНСТИТУТ КОМП’ютерних НАУК та ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ Кафедра “Системи автоматизованого проектування”
ЗВІТ до лабораторної роботи №4 на тему «ДОСЛІДЖЕННЯ АЛГОРИТМІВ РОЗПІЗНАВАННЯ ОБРАЗІВ.АЛГОРИТМ “ІСОМАД (ISODATA)”» з курсу «Системи штучного інтелекту» Виконав: ст. гр. КН-3 Львів-2008 1.Мета роботи Вивчити основні принципи роботи алгоритму розпізнавання образів ІСОМАД. Короткі теоретичні відомості 2.1. Алгоритм ІСОМАД Крок 1 Задаються параметри, що визначають процес кластеризації: К - необхідна кількість кластерів;
- параметр, з яким порівнюється кількість вибіркових образів, що ввійшли в кластер;
- параметр, що характеризує середньоквадратичне відхилення;
- параметр, що характеризує компактність; L - максимальна кількість пар центрів кластерів, які можна об’єднати; І - допустима кількість циклів і ітерацій. Крок 2 Задані N образів розподіляються по кластерах, що відповідають вибраним початковим цетрам за правилами
якщо
i=1,2, ... , Nc ,
Крок 3 Ліквідуються підмножини образів, в склад яких входять менше
елементів, т.б. якщо для деяког j виконується умова Nj<
, то підмножини Sj виключається із перегляду і значення Nc зменшується по 1. Крок 4 Кожен центр кластера Zj , j =1,2, ... , Nc, локалізується і коректується
j=1,2, ... ,Nc де Nj - число об’єктів, що ввійшли в підмножину Sj. Крок 5 Обчислюється середня відстань
між об’єктами, що входять в підмножину
, і відповідним центром кластера за формулою:
, j=1,2,...,
. Крок 6 Обчислюється узагальнене середня відстань між об’єктами, що знаходяться в окремих кластерах, і відповідними центрами кластерів за формулою:
Крок 7 а) Якщо біжучий цикл ітерації - останній, то задається
; перехід до 11. б) Якщо умова
виконуєтьяс то перехід до кроку 8. в) Якщо біжучий цикл ітерацій має перший порядковий номер, або виконується умова
, то перехід на крок 11; інакше крок 8 Крок 8 Для кожної підмножини вибіркових образів за допомогою співвідношення:
, і=1,2,..., n; j=1,2,...,
вираховуєтьяс вектор середньоквадратичного відхилення
, де n є розмірність образа, Хik є і-ю компонентою к-го об’єктів підмножини Sj, Zij є і-ю компонентою вектора, що представляє центр кластера Zj , i Nj - кількість вибіркових образів, включених в підмножину Sj. Кожна компонента вектора середнього квадратичного відхилення
характеризує середньоквадратичне відхилення образу, що входить в півмножину Sj, по одній із головних осей координат. Крок 9 В кожному векторі середньоквадратичного відхилення
, j=1,2,...,Nc, виконуються умови
мах >
і а)

або б)
,
то кластер з центром Zj розщеплюється на два повних кластера з центрами
і
відповідно, кластера із центром
ліквідується, а значення
збільшується на 1. Для визначення центра кластера
до компонент вектора
, що відповідає максимальній компоненті вектора
, додається задана величина
; центр кластера
визначається відніманням цієї ж величини
із цієї компоненти вектора Z,
Якщо розщеплення відбувається на даному кроці, то перейти на крок 2, інакше крок 11. Крок 11 Вираховується відстані
між усіма парами центрів кластерів
Крок 12 Відстані
порівнюються з параметрами
. Ті < вітдалей, які виявилися меншими за
ранжуються в порядку зростання
; Причому
, а L - max кількість пар центрів кластерів, які можна об’єднати. Крок 13 Кожна віддаль Dieje вирахувано для певної пари кластерів із центрами Zil Zjl. До цих пар послідовності, що відповідає збільшенню відстані між центрами, застосовується процедура злиття: кластери з центрами Zil і Zjl, l=1,2,...,L, об’єднуються (при умові, що в біжучому циклі ітерації процедура злиття не застосовувалася ні до того, ні до іншого кластера), причому новий центр кластера визначається за формулою
Центри кластерів Zil i Zjl ліквідуються і значення Nc зменшується по1. Допускається лише по...